#include <iostream>

/** 
 * Partitioning the array.
 * 
 * @param arr The pointer to the first element of the array.
 * @param n Total number of the elements.
 * 
 * @return Error code, 0 for OK.
 */template<typename T> int partition(T *arr, int n);

/** 
 * An implement for quicksort.
 * 
 * @param arr The pointer to the first element to sort.
 * @param n The element from arr to arr + n - 1 will be sorted.
 * 
 * @return The index of the pivot.
 */
template<typename T> int quicksort(T *arr, int n);

/** 
 * An optimization for quicksort, when n less than 4, we use 
 * direct method instead of recursion.
 * 
 * @param arr The pointer to the first element to sort.
 * @param n The element from arr to arr + n - 1 will be sorted.
 * 
 * @return The index of the pivot.
 */
template<typename T> int opti_quicksort(T *arr, int n);

template<typename T> int opti_quicksort(T *arr, int n)
{
    if (n > 3)
    {
	int p = partition(arr, n);
	quicksort(arr, p);
	quicksort(arr + p + 1, n - p - 1);
	return 0;
    }
    else
    {
	if (n == 0 || n == 1)
	    return 0;
	else if (n == 2)
	{
	    if (arr[0] > arr[1])
	    {
		T tmp = arr[0];
		arr[0] = arr[1];
		arr[1] = tmp;
	    }
	    return 0;
	}
	else if (n == 3)
	{
	    T tmp;
	    if (arr[1] <= arr[0] && arr[1] <= arr[2])
	    {
		if (arr[0] <= arr[2])
		{
		    tmp = arr[1];
		    arr[1] = arr[0];
		    arr[0] = tmp;
		}
		else
		{
		    tmp = arr[2];
		    arr[2] = arr[0];
		    arr[0] = arr[1];
		    arr[1] = tmp;
		}
	    }
	    else if (arr[2] <= arr[0] && arr[2] <= arr[1])
	    {
		if (arr[0] <= arr[1])
		{
		    tmp = arr[0];
		    arr[0] = arr[2];
		    arr[2] = arr[1];
		    arr[1] = tmp;
		}
		else
		{
		    tmp = arr[2];
		    arr[2] = arr[0];
		    arr[0] = tmp;
		}
	    }
	    return 0;
	}
	return -1;
    }
};

template<typename T> int quicksort(T *arr, int n)
{
    if (n > 0)
    {
	int p = partition(arr, n);
	quicksort(arr, p);
	quicksort(arr + p + 1, n - p - 1);
    }
    return 0;
};

template<typename T> int partition(T *arr, int n)
{
    if (n <= 0)
	return 0;
    int left = 0;
    int right = n - 1;
    T pivot = arr[0];
    while (left != right)
    {
	while (arr[right] >= pivot && right > left)
	    right--;
	while (arr[left] <= pivot && right > left)
	    left++;
	if (right > left)
	{
	    T tmp = arr[left];
	    arr[left] = arr[right];
	    arr[right] = tmp;
	    right--;
	}
    }
    arr[0] = arr[left];
    arr[left] = pivot;
    return left;
};



#include <cmath>
#define PI (std::atan(1.0) * 4.0)
#define E (std::exp(1))

int main(int argc, char *argv[])
{
    double A[5] = {PI, PI, E, 0.0, 1.0};

    std::cout << "Before: A = [";
    for (int i = 0; i < 5; i ++)
	std::cout << A[i] << ", ";
    std::cout << "\b\b]" << std::endl;
    opti_quicksort(A, 5);
    std::cout << "After: A = [";
    for (int i = 0; i < 5; i ++)
	std::cout << A[i] << ", ";
    std::cout << "\b\b]" << std::endl;
    
    return 0;
};
